public class LC0238 {
    /**
     * 时间复杂度O(N)，空间复杂度O(N)
     * @param nums
     * @return
     */
    public static int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] prefix = new int[length]; // 前面各数字的乘积
        int[] postfix = new int[length];

        prefix[1] = nums[0];
        postfix[length - 1 - 1] = nums[length - 1];
        for (int i = 2; i < length; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
            postfix[length - 1 - i] = nums[length - 1 - i + 1] * postfix[length - 1 - i + 1];
        }

        int[] retArray = new int[length];
        retArray[0] = postfix[0];
        retArray[length - 1] = prefix[length - 1];

        for (int i = 1; i < length - 1; i++) {
            retArray[i] = prefix[i] * postfix[i];
        }

        return retArray;
    }

    /**
     * 除输出数组外空间复杂度为O(1)
     */
    public static int[] productExceptSelfConstSpace(int[] nums) {
        int length = nums.length;
        int[] retArray = new int[length];

        retArray[0] = 1;
        retArray[1] = nums[0];
        for (int i = 2; i < length; i++) { // 前缀数字乘积
            retArray[i] = nums[i - 1] * retArray[i - 1];
        }
        int postfixProduct = 1; // 暂存后缀数字乘积
        int tmpPrefix;
        for (int i = length - 1 - 1; i >= 0; i--) {
            postfixProduct *= nums[i + 1];
            tmpPrefix = retArray[i]; // 暂存前缀积
            retArray[i] = retArray[i] * postfixProduct; // 更新为前缀积*后缀积
        }

        return retArray;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4};
        System.out.println(productExceptSelfConstSpace(nums));
    }
}
